package com.explorati.LeetCode143.reorderList;

import java.util.ArrayList;
import java.util.List;

/**
 * @ Author : Weijian_Wang
 * @ Date : Created in 22:57 2020/10/21 0021
 * @ Description ：
 */
public class Solution {


      public class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      }

    /**
     * 给定链表 1->2->3->4, 重新排列为 1->4->2->3
     * 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
     * @param head
     */
    public void reorderList(ListNode head) {
        if(head == null) {
            return ;
        }
        List<ListNode> list = new ArrayList<>();
        ListNode node = head;
        while(node != null) {
            list.add(node);
            node = node.next;
        }
        int i = 0;
        int j = list.size() - 1;
        while(i < j) {
            list.get(i).next = list.get(j);
            i ++;
            if(i == j) {
                break;
            }
            list.get(j).next = list.get(i);
            j --;
        }
        list.get(i).next = null;
    }
}
